Elevator II

The 2024 ICPC Asia Hangzhou Regional Contest E Elevator II

Question

有一部电梯，$n$ 个人，第 $i$ 个人需要从第 $l_i$ 层到第 $r_i$ 层（$l_i<r_i$），电梯上升一层需要 1 的代价，下降不需要代价，电梯刚开始在第 $f$ 层，电梯一次只能带一个人

需要你构造出一个排列，保证能满足所有人的需求，并且代价最小

输出最小代价和排列

Solution

考虑答案的上界

首先，每一趟电梯的距离是不可以省去的，即 $\sum (r_{a_i}-l_{a_i})$

还有就是从 $f$ 到 $max\{r\}$ 这趟距离

我们很容易可以构造出这样的方法，第一步就是从 $f$ 到 $max\{r\}$ 然后把电梯按照 $r$ 排序，从大到小运送即可

但是其实我们在从 $f$ 到 $max\{r\}$ 的过程中可以顺带着把一些人带上去，这里就用到了贪心的想法

如果当前我们在的位置是 $p$ 那么我们可以选择 $l$ 小于 $p$ 且 $r$ 大于 $p$ 的那个人送上去，如果不存在这样的人，就去找下一个 $l$ 最小的那个人，这可以用一个指针完成

Code

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int l, r, id;
};

bool cmpl(const Node &a, const Node &b) {
    return a.l < b.l || (a.l == b.l && a.r > b.r);
}

bool cmpr(const Node &a, const Node &b) {
    return a.r > b.r;
}


void solve() {
    int n, f; cin >> n >> f;
    vector<Node> a(n + 1);

    for (int i = 1; i <= n; i++) {
        cin >> a[i].l >> a[i].r;
        a[i].id = i;
    }

    sort(a.begin() + 1, a.end(), cmpl);
    vector<int> ans;
    vector<int> vis(n + 1, 0);

    long long sum = 0;
    int now = f;
    for (int i = 1; i <= n; i++) {
        if (a[i].l <= now && a[i].r <= now) continue;
        if (a[i].l > now) sum += a[i].l - now;
        sum += a[i].r - a[i].l;
        ans.push_back(a[i].id);
        vis[a[i].id] = 1;
        now = a[i].r;
    }

    sort(a.begin() + 1, a.end(), cmpr);
    for (int i = 1; i <= n; i++) {
        if (vis[a[i].id]) continue;
        sum += a[i].r - a[i].l;
        ans.push_back(a[i].id);
        vis[a[i].id] = 1;
    }

    cout << sum << "\n";
    for (auto id : ans)
        cout << id << " ";    
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int t; cin >> t;
    while (t--) solve();
    return 0;
}